// 给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

// 返回所有可能的结果。答案可以按 任意顺序 返回。
#include<bits/stdc++.h>
using namespace std;

// 看了题解

// 执行用时：
// 4 ms
// , 在所有 C++ 提交中击败了
// 89.31%
// 的用户
// 内存消耗：
// 7.6 MB
// , 在所有 C++ 提交中击败了
// 87.06%
// 的用户

class Solution {
public:
    vector<string> res;
    vector<string> removeInvalidParentheses(string s) {
        int left=0,right=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                left++;
            }
            else if(s[i]==')'){
                if(left>0){
                    left--;
                }
                else{
                    right++;
                }
            }
        }
        int start=0;
        dfs(start,left,right,s);
        return res;

    }

    void dfs(int start,int left,int right,string s){
        if(left==0 && right==0){
            if(is_valid(s)){
                res.push_back(s);
            }
        }
        for(int i=start;i<s.size();i++){
            // 与前面相同，则已经进行过判断，跳过
            if(i!=start &&s[i-1]==s[i]){
                continue;
            }
            else if(s[i]=='('&&left>0){
                dfs(i,left-1,right,s.substr(0,i)+s.substr(i+1,s.size()-1-i));
            }
            else if(s[i]==')'&&right>0){
                dfs(i,left,right-1,s.substr(0,i)+s.substr(i+1,s.size()-1-i));
            }
        }
    }

    bool is_valid(string& s){
        int l=0,r=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                l++;
            }
            else if(s[i]==')'){
                if(l>0){
                    l--;
                }
                else{
                    r++;
                }
            }
        }
        if(l==0 && r==0){
            return true;
        }
        return false;
    }
};